package com.egg.nqueen;

public class QueenProblem {
	private boolean[][] stage;
	private int size;

	public QueenProblem(int n) {
		stage = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				stage[i][j] = false;
			}
		}
		size = n;
	}

	public boolean nQueen(int row) {
		if (row == size) {
			return true;
		}

		if (row == -1) {
			return false;
		}

		for (int i = 0; i < size; i++) {
			stage[row][i] = true;

			if (valid()) {
				if (nQueen(row + 1)) {
					return true;
				} else {
					stage[row][i] = false;
				}
			} else {
				stage[row][i] = false;
			}
		}

		return false;
	}

	public boolean valid() {
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (stage[i][j] && !check(i, j)) {
					return false;
				}
			}
		}

		return true;
	}

	private boolean check(int row, int col) {
		for (int i = 0; i < size; i++) {
			if (i != row && stage[i][col]) {
				return false;
			}
		}

		for (int i = row + 1, j = col + 1; i < size && j < size; i++, j++) {
			if (stage[i][j]) {
				return false;
			}
		}

		for (int i = row - 1, j = col - 1; i > 0 && j > 0; i--, j--) {
			if (stage[i][j]) {
				return false;
			}
		}

		for (int i = row - 1, j = col + 1; i > 0 && j < size; i--, j++) {
			if (stage[i][j]) {
				return false;
			}
		}

		for (int i = row + 1, j = col - 1; i < size && j > 0; i++, j--) {
			if(stage[i][j]) {
				return false;
			}
		}

		return true;
	}

	public void setStage(boolean[][] bs) {
		this.stage = bs;
	}

	public void print() {
		for (int i = 0; i < stage.length; i++) {
			for (int j = 0; j < stage[i].length; j++) {
				System.out.print(stage[i][j] ? "*" : "-");
			}
			System.out.println();
		}
	}
}